package com.nav.util;

import java.io.Serializable;
import java.util.HashMap;
import java.util.Map;

public class SpellingCorrector implements Serializable {
	private static final long serialVersionUID = 1L;
	private String dictionary[];

	public SpellingCorrector(String dictionary[]) {
		this.dictionary = dictionary;
	}

	private static int getDamerauLevenshteinDistance(String source, String target)
	{
		if (source == null || source.length() <= 0)
		{
			if (target == null || target.length() <= 0)
				return 0;
			else
				return target.length();
		}
		else if (target == null || target.length() <= 0)
			return source.length();

		int score[][] = new int[source.length() + 2][target.length() + 2];

		int INF = source.length() + target.length();
		score[0][0] = INF;
		for (int i = 0; i <= source.length(); i++) { score[i + 1][1] = i; score[i + 1][0] = INF; }
		for (int j = 0; j <= target.length(); j++) { score[1][j + 1] = j; score[0][j + 1] = INF; }

		Map<Character, Integer> sd = new HashMap<Character, Integer>();
		char letters[] = (source + target).toCharArray();
		for (char letter : letters)
		{
			if (!sd.containsKey(letter))
				sd.put(letter, 0);
		}

		for (int i = 1; i <= source.length(); i++)
		{
			int DB = 0;
			for (int j = 1; j <= target.length(); j++)
			{
				int i1 = sd.get(target.charAt(j - 1));
				int j1 = DB;

				if (source.charAt(i - 1) == target.charAt(j - 1))
				{
					score[i + 1][j + 1] = score[i][j];
					DB = j;
				}
				else
					score[i + 1][j + 1] = java.lang.Math.min(score[i][j], java.lang.Math.min(score[i + 1][j], score[i][j + 1])) + 1;

				score[i + 1][j + 1] = java.lang.Math.min(score[i + 1][j + 1], score[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
			}

			sd.put(source.charAt(i - 1), i);
		}

		return score[source.length() + 1][target.length() + 1];
	}

	/**
	 * For given word, return closest match correct spelling
	 *
	 * @param word
	 * @return
	 */
	public String correctWord(String word) {
		int md = Integer.MAX_VALUE;
		String mdw = word;
		for(int i = 0; i < dictionary.length; i++) {
			int d = getDamerauLevenshteinDistance(word, dictionary[i]);
			if(d < md) {
				md = d;
				mdw = dictionary[i];
			}
		}
		if(md <= word.length() / 2)
			return mdw;
		return word;
	}
}
